package com.datastructure2.monotonicstack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

/**
 * @author: 临晖
 * @date: 2024/03/22
 * @description:
 */
public class Solution {


    /**
     *
     * 739. 每日温度
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
     *
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        if (temperatures.length <= 1) {
            return new int[]{0};
        }

        Stack<Integer> stack = new Stack<>();
        int[] res = new int[temperatures.length];
        stack.add(0);

        for (int i = 1; i < temperatures.length; i++) {
            Integer top = stack.peek();

            while (!stack.isEmpty() && temperatures[i] > temperatures[top]) {
                stack.pop();        //弹出
                res[top] = i - top;

                if (!stack.isEmpty()) {
                    top = stack.peek();  //继续查看
                }

            }

            stack.push(i);
        }
        return res;
    }


    /**
     *
     * 496. 下一个更大元素 I
     * 简单
     * 相关标签
     * 相关企业
     * nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
     * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
     * 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
     * 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();        //数字x，比它打的第一个数
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums2.length; i++) {
            if (stack.isEmpty()) {      //如果栈为空，则直接入栈
                stack.push(i);
                continue;
            }

            Integer topIndex = stack.peek();
            while (!stack.isEmpty() && nums2[i] > nums2[topIndex]) {
                stack.pop();        //弹出
                map.put(nums2[topIndex], nums2[i]);

                if (!stack.isEmpty()) {
                    topIndex = stack.peek();
                }
            }

            stack.push(i);
        }

        int[] res = new int[nums1.length];
        for (int i = 0; i  < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }

        return res;
    }


    /**
     *
     * 503. 下一个更大元素 II
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
     * 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
     *
     * @param nums
     * @return
     */
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int[] newNums = Arrays.copyOf(nums, 2 * len);

        for (int i = 0; i < len; i++) {
            newNums[i + len] = nums[i];
        }

        Stack<Integer> stack = new Stack<>();
        int[] res = new int[len];
        Arrays.fill(res, -1);

        for (int i = 0; i < 2 * len; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
                continue;
            }

            Integer topIndex = stack.peek();
            while (!stack.isEmpty() && newNums[i] > newNums[topIndex]) {
                stack.pop();        //弹出

                if (topIndex < len) {
                    res[topIndex] = newNums[i];
                }

                if (!stack.isEmpty()) {
                    topIndex = stack.peek();
                }
            }

            stack.push(i);
        }

        return res;
    }


    /**
     *
     * 42. 接雨水
     * 困难
     * 相关标签
     * 相关企业
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        stack.push(0);
        for (int i = 1; i < height.length; i++) {

            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                Integer topIndex = stack.pop();        //弹出
                if (!stack.isEmpty()) {

                    int heig = Math.min(height[stack.peek()], height[i]) - height[topIndex];
                    int weig = i - stack.peek() - 1;
                    sum += (heig * weig);
                }


            }

            stack.push(i);
        }

        return sum;
    }


    /**
     *
     * 84. 柱状图中最大的矩形
     * 困难
     * 相关标签
     * 相关企业
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     *
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int[] arr = new int[heights.length + 2];
        for (int i = 0; i < heights.length; i++) {
            arr[i + 1] = heights[i];
        }

        heights = arr;

        int res = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 1; i < heights.length; i++) {

            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                Integer mind = stack.pop();
                int left = stack.peek();

                res  = Math.max(res, (i - left - 1 ) * heights[mind]);
            }


            stack.push(i);
        }

        return res;
    }


    @Test
    public void myTest() {
        trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
        //nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2});

        //dailyTemperatures(new int[]{73,74,75,71,69,72,76,73});
    }




}
